// 807. 保持城市天际线

function maxIncreaseKeepingSkyline(grid: number[][]): number {
  // 记录行列中最高建筑的高度
  const rowMax = new Array(grid.length).fill(0);
  const colMax = new Array(grid.length).fill(0);
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid.length; j++) {
      // 便利矩阵 寻找行列最高建筑的高度
      rowMax[i] = Math.max(rowMax[i], grid[i][j]);
      colMax[j] = Math.max(colMax[j], grid[i][j]);
    }
  }

  let ans = 0;

  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid.length; j++) {
      // 建筑物最多能增加的高度不能超过行列中最高建筑中的最小值 所以取行列最小值减去当前建筑物高度 并将结果累加
      ans += Math.min(rowMax[i], colMax[j]) - grid[i][j];
      // console.log()
    }
  }

  return ans;
}

const grid = [
  [3, 0, 8, 4],
  [2, 4, 5, 7],
  [9, 2, 6, 3],
  [0, 3, 1, 0],
];
console.log(maxIncreaseKeepingSkyline(grid));
